#include <iostream>
#include <vector>
#include <queue>
#include <math.h>
using namespace std;
class State{
public:
    int location;
    int path;
    State(int p, int l) :location(l), path(p) {}
};
/*
 * leetcode 847
给出graph为有 N 个节点（编号为0, 1, 2, ..., N-1）的无向连通图。
graph.length = N，且只有节点 i和 j连通时，j != i在列表graph[i]中恰好出现一次。
返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。
 */
class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<vector<int>> dist(1<<n, vector<int>(n, -1));
        queue<State> que;

        for(int i=0; i<n; ++i){
            que.push(State(1<<i, i));
            dist[1<<i][i] = 0;
        }

        while(!que.empty()){
            auto state = que.front();
            que.pop();
            int d = dist[state.path][state.location];
            if(state.path == pow(2,n)-1)
                return d;
            for(auto next_location : graph[state.location]){
                int next_path = state.path | 1 << next_location;
                if(dist[next_path][next_location] == -1 || dist[next_path][next_location] > d + 1){
                    que.push(State(next_path, next_location));
                    dist[next_path][next_location] = d + 1;
                }
            }
        }
        return -1;
    }
};
/*
华为题 leetoce847改编后的题目
给出graph为有 N 个节点（编号为0, 1, 2, ..., N-1）的无向连通图。
graph.length = N，且只有节点 i和 j连通时，j != i在列表graph[i]中恰好出现一次。
返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，不可以重访节点，不可以重用边。
 */
class Solution2 {
public:
    int shortestPathLength(vector<vector<int>>& graph, vector<vector<int>>& distance, int n) {
        vector<vector<int>> dist(1<<n, vector<int>(n, -1));
        queue<State> que;
        vector<int> res;

//        for(int i=0; i<n; ++i){
//            que.push(State(1<<i, i));
//            dist[1<<i][i] = 0;
//        }

        que.push(State(1<<0, 0));
        dist[1<<0][0] = 0;


        while(!que.empty()){
            auto state = que.front();
            que.pop();
            int d = dist[state.path][state.location];
            if(state.path == pow(2,n)-1){
                res.push_back(d);
            }
            for(auto next_location : graph[state.location]){
                if ((state.path & (1<<next_location)) != 0){
                    continue;
                }
                int next_path = state.path | 1 << next_location;
                que.push(State(next_path, next_location));
                dist[next_path][next_location] = d + distance[state.location][next_location];
            }
        }
        if(res.empty())
            return -1;
        else{
            int ans = res[0];
            for(auto x : res)
                ans = min(ans, x);
            return ans;
        }
    }
};

const int M =15;
int main() {
    freopen("1.in","r",stdin);
    vector<vector<int>> distance(M, vector<int>(M, -1));
    vector<vector<int>> graph(M);
    int m, start, n;
    cin >> m >> start >> n;
    for(int i=0; i<n; ++i){
        int x, y, d;
        cin >> x >> y >> d;
        distance[x][y] = d;
        distance[y][x] = d;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

//    for(auto node : graph){
//        for (auto judge : node)
//            cout << judge << " ";
//        cout << endl;
//    }
//    cout << "input finished" << endl;
    Solution2 slove = Solution2();
    cout << slove.shortestPathLength(graph, distance, m)<<endl;

    return 0;
}
/*
4 0 4
0 1 1
0 2 1
0 3 1
1 2 1

4 0 4
0 1 1
1 2 1
2 3 1
1 3 2
 */